package com.ywk.base.dataStructure.binarytree;

public class ThreadBinaryTreeDemo {

	public static void main(String[] args) {
		int[] arr= {1,3,6,8,10,14}; 
		ThreadBinaryTree tbt1=new ThreadBinaryTree(arr);
		tbt1.preOrder(0);
//		Node n1=new Node(1);
//		Node n2=new Node(3);
//		Node n3=new Node(6);
//		Node n4=new Node(8);
//		Node n5=new Node(10);
//		Node n6=new Node(14);
//		n1.setLeft(n2);
//		n1.setRight(n3);
//		n2.setLeft(n4);
//		n2.setRight(n5);
//		n3.setLeft(n6);
//		ThreadBinaryTree tbt=new ThreadBinaryTree();
//		tbt.InThreadNode(n1);
//		System.out.println(n5.getLeft());
//		System.out.println(n5.getRight());
//		tbt.threadList(n1);
	}
}

class ThreadBinaryTree{
	private Node root;
	private Node pre;//作用于递归时，多个threadNode方法共用该变量，只能声明为私有成员变量，
	private int[] arr;
	private int flag=0;
	public ThreadBinaryTree() {
		super();
	}
	
	public ThreadBinaryTree(int[] arr) {
		super();
		this.arr = arr;
	}
	
	public ThreadBinaryTree(Node root) {
		super();
		this.root = root;
	}
	
	public void preOrder(int index) {
		Node node=new Node(arr[index]);
		if (2 * index + 1 < arr.length) {
			flag=0;
			preOrder(2 * index + 1);
			flag=0;
		}
		if(2*index+1<arr.length&&node.getLeft()==null) {
			node.setLeft(pre);
		}
		if(flag==1&&index<arr.length&&pre.getRight()==null) {
			pre.setRight(node);
		}
		if(flag==0){
			pre=node;
		}
		if (2 * index + 2 < arr.length) {
			flag=1;
			preOrder(2 * index + 2);
		}
	}
	
	//前序二叉树线索化
	public void PreThreadNode(Node node) {
		if(node==null) {
			return;
		}
		//处理当前结点
		if(node.getLeft()==null) {
			node.setLeft(pre);
			node.setLeftType(1);
		}
		if(pre!=null&&pre.getRight()==null) {
			pre.setRight(node);
			pre.setRightType(1);
		}
		pre=node;
		//递归左子树
		PreThreadNode(node.getLeft());
		//递归右子树
		PreThreadNode(node.getRight());
	}
	
	//中序线索化二叉树
	public void InThreadNode(Node node){
		if(node==null) {
			return;
		}
		//递归左子树
		InThreadNode(node.getLeft());
		//处理当前结点
		if(node.getLeft()==null) {
			node.setLeft(pre);//前驱结点的指向
			node.setLeftType(1);
		}
		if(pre!=null&&pre.getRight()==null) {
			pre.setRight(node);//后继结点的指向
			pre.setRightType(1);
		}
		pre=node;
		//递归右子树
		InThreadNode(node.getRight());
	}
	
	
	
	//遍历线索二叉树(优点：)
	public void threadList(Node root) {
		Node node=root;
		while(node!=null) {
			//通过leftType=1的标记找到左子树的最后一个左子结点左子树
			while(node.getLeftType()==0) {
				node=node.getLeft();
			}
			//打印当前结点
			System.out.println(node);
			//
			while(node.getRightType()==1) {
				node=node.getRight();
				System.out.println(node);
			}
			node=node.getRight();
		}
	}
}


class Node{
	private int no;
	private Node left;
	private Node right;
	
	private int leftType;
	private int rightType;
	
	public Node(int no) {
		super();
		this.no = no;
	}

	public int getNo() {
		return no;
	}

	public void setNo(int no) {
		this.no = no;
	}

	public Node getLeft() {
		return left;
	}

	public void setLeft(Node left) {
		this.left = left;
	}

	public Node getRight() {
		return right;
	}

	public void setRight(Node right) {
		this.right = right;
	}

	public int getLeftType() {
		return leftType;
	}

	public void setLeftType(int leftType) {
		this.leftType = leftType;
	}

	public int getRightType() {
		return rightType;
	}

	public void setRightType(int rightType) {
		this.rightType = rightType;
	}

	@Override
	public String toString() {
		return "Node [no=" + no + "]";
	}	
}








